<html>
<head>
  <title>Evernote Export</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="YXBJ Windows/603139 (zh-CN, DDL); Windows/10.0.0 (Win64); EDAMVersion=V2;"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="592"/>

<div>
<span><div><div>数据结构： 数据结构(data structure)是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定 关系的数据元素的集合。也就是 存数据的，而且是在内存中存！</div><div>常见的数据结构：</div><div>线性表：数组，链表，栈，队列</div><div>散列表：hash,位图</div><div>树：二叉树，多路树，堆</div><div>图：有向图，无向图，带权图</div><div><br/></div><div>算法概念： 指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用 系统的方法描述解决问题的策略机制。也就是说： 算法是一种解决特定问题的思路</div><div>eg: LRU算法，最近最少使用，解决的就是当空间不够用时，应该淘汰谁的问题，这是一种策略，不 是唯一的答案，所以算法无对错，只有好和不好。</div><div><br/></div><div>常见算法：</div><div>排序：冒泡：快速，插入，归并，计数排序，选择排序，堆排序，桶排序</div><div>算法思维：递归，回溯，分治，贪心动态规划</div><div><br/></div><div>算法复杂度： 数据结构和算法本质上是”快“和&quot;省&quot;。所以代码的执行效率是非常重要的度量 我们采用时间复杂度和空间复杂度来计算</div><div>计算时间复杂度的技巧：</div><ol><li><div>计算循环执行次数最多的代码</div></li><li><div>总复杂度=量级最大的复杂度</div></li></ol><div><br/></div><div>常见的时间复杂度</div><ol><li><div>O(1) 这种是最简单的，也是最好理解的，就是常量级 不是只执行了一行代码，只要代码的执行不随着数据规模(n)的增加而增加，就是常量级 在实际应用中，通常使用冗余字段存储来将O(n)变成O(1)，比如Redis中有很多这样的操作用来提 升访问性能 比如:SDS、字典、跳跃表等</div></li></ol><div><br/></div><div>空间复杂度：全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系</div><div><br/></div><div><br/></div><div>线性表： 就是数据排成像一条线一样的结构，数据只有前后两个方向</div><div>数组： 是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是 最为简单、最为常用的数据结构。</div><div>存储原理： 数组用一组连续的内存空间来存储一组具有相同类型的数据</div><div>数组可以根据下标随机访问数据</div><div>读取元素： 根据下标读取元素的方式叫作随机读取</div><div>更新元素不要数组越界</div><div>读取和更新都可以随机访问，时间复杂度为O(1)</div><div>插入元素可分为：</div><ol><li><div>尾部插入： 在数据的实际元素数量小于数组长度的情况下： 直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作</div></li><li><div>中间插入： 在数据的实际元素数量小于数组长度的情况下： 由于数组的每一个元素都有其固定下标，所以首先把插入位置及后面的元素向后移动，腾出地方， 再把要插入的元素放到对应的数组位置上。</div></li><li><div>超范围插入 假如现在有一个数组，已经装满了元素，这时还想插入一个新元素，或者插入位置是越界的 这时就要对原数组进行扩容：可以创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素统 统复制 过去，这样就实现了数组的扩容。</div></li></ol><div>删除元素： 数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪 动1位。</div><div>时间复杂度： 读取和更新都是随机访问，所以是O(1) 插入数组扩容的时间复杂度是O(n)，插入并移动元素的时间复杂度也是O(n)，综合起来插入操作的时间 复杂度是O(n)。 删除操作，只涉及元素的移动，时间复杂度也是O(n)</div><div><br/></div><div>优点： 数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素</div><div>缺点：</div><ol><li><div>插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫 移动，影响效率。 (ArrayList LinkedList )</div></li><li><div>申请的空间必须是连续的，也就是说即使有空间也可能因为没有足够的连续空间而创建失败</div></li><li><div>如果超出范围，需要重新申请内存进行存储，原空间就浪费了</div></li></ol><div>应用： ArrayList、Redis、消息队列等等。</div><div><br/></div><div>链表：概念： 一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。 链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元 素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据 域，另一个是存储下一个结点地址的指针域</div><div><br/></div><div>常见的链表包括：单链表、双向链表、循环链表</div><div>单链表： 单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节 点的指针next</div><div>双向链表： 双向链表的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。</div><div>循环链表： 链表的尾节点指向头节点形成一个环，称为循环链表</div><div>存储原理： 数组在内存中的存储方式是顺序存储（连续存储），链表在内存中的存储方式则是随机存储（链式存 储）。 链表的每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎 片空间。 链表的第1个节点被称为头节点（3），没有任何节点的next指针指向它，或者说它的前置节点为空 头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表 链表的最后1个节点被称为尾节点（2），它指向的next为空</div><div>查找节点 在查找元素时，链表只能从头节点开始向后一个一个节点逐一查找。</div><div>更新节点 找到要更新的节点，然后把旧数据替换成新数据</div><div>尾部插入 把最后一个节点的next指针指向新插入的节点即可</div><div>头部插入 第1步，把新节点的next指针指向原先的头节点 第2步，把新节点变为链表的头节点</div><div>中间插入 第1步，新节点的next指针，指向插入位置的节点 第2步，插入位置前置节点的next指针，指向新节点</div><div>只要内存空间允许，能够插入链表的元素是无限的，不需要像数组那样考虑扩容的问题</div><div>删除节点 尾部删除 把倒数第2个节点的next指针指向空即可</div><div>头部删除 把链表的头节点设为原先头节点的next指针即可</div><div><br/></div><div>中间删除 把要删除节点的前置节点的next指针，指向要删除元素的下一个节点即可</div><div><span style="color: unset; font-family: unset; font-size: unset;">优势 插入、删除、更新效率高 省空间 </span></div><div><span style="color: unset; font-family: unset; font-size: unset;">劣势 查询效率较低，不能随机访问</span><br/></div><div>数组与链表的对比：</div><div>数据结构没有绝对的好与坏，数组和链表各有千秋。</div><div>数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些 </div><div>链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更合适 一些 </div><div>数组和链表是线性数据存储的物理存储结构：即顺序存储和链式存储。</div><div>栈和队列都属于线性数据的逻辑存储结构</div><div>栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。 最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶 （top）。</div><div>栈既可以用数组来实现，也可以用链表来实现</div><div>入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为 新的栈顶</div><div>出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会 成为新的栈顶。</div><div>队列（queue）是一种线性数据结构，队列中的元素只能先入先出（First In First Out，简称 FIFO）。 队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。</div><div>队列这种数据结构既可以用数组来实现，也可以用链表来实现</div><div>用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置 用数组实现的队列叫作顺序队列</div><div>用链表实现的队列叫作链式队列</div><div>入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位 置将会成为新的队尾。</div><div>出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元 素将会成为新的队头。</div><div>散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要 给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)。</div><div>存储原理 </div><div>哈希函数 </div><div>散列表在本质上也是一个数组 </div><div>散列表的Key则是以字符串类型为主的 </div><div>通过hash函数把Key和数组下标进行转换 </div><div>作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值</div><div>写操作就是在散列表中插入新的键值对（在JDK中叫作Entry或Node）</div><div>由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可 能是相同的，这种情况，就叫作哈希冲突。</div><div>开放寻址法的原理是当一个Key通过哈希函数获得对应的数组下标已被占用时，就寻找下一个空档 位置</div><div>数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针 指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链 表中即可，默认next指向null</div><div>递归算法是一种 直接或者间接调用自身函数或者方法的算法</div><div>递归，去的过程叫&quot;递&quot;，回来的过程叫”归“</div><div>递是调用，归是结束后回来 </div><div>是一种循环，而且在循环中执行的就是调用自己 </div><div>递归调用将每次返回的结果存在栈帧中</div><div>递归三要素：</div><ol><li><div>递归结束条件 既然是循环就必须要有结束，不结束就会OOM了</div></li><li><div>函数的功能 这个函数要干什么，打印，计算.... 函数的等价关系式</div></li><li><div>递归公式，一般是每次执行之间，或者与个数之间的逻辑关系</div></li></ol><div>二分查找（Binary Search）算法，也叫折半查找算法： 是针对有序数据集合的查找算法，如果是无序数据集合就遍历查找</div><div>二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能 包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。</div><div><span style="color: unset; font-family: unset; font-size: unset;">优点：速度快，不占空间，不开辟新空间 </span><br/></div><div>缺点：必须是有序的数组，数据量太小没有意义，但数据量也不能太大，因为数组要占用连续的空间</div><div>有序的查找都可以使用二分法。</div><div><br/></div><div>二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有2个孩子节 点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。</div><div>二叉树节点的两个孩子节点，一个被称为左孩子（left child），一个被称为右孩子（right child）。这 两个孩子节点的顺序是固定的，左孩子小于右孩子。</div><div>一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就 是满二叉树</div><div>对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同 样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树</div><div>二叉树属于逻辑结构，可以使用链表和数组进行存储。</div><div>二叉树的后序遍历，输出顺序是左子树、右子树、根节点</div><div>二叉树的中序遍历，输出顺序是左子树、根节点、右子树</div><div>二叉树的前序遍历，输出顺序是根节点、左子树、右子树</div><div>广度优先遍历 也叫层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各 个节点。</div><div>二叉树同一层次的节点之间是没有直接关联的，利用队列可以实现</div><div>红黑树： 自平衡的二叉查找树。</div><div>特征：</div><ol><li><div>每个节点要么是黑色，要么是红色</div></li><li><div>根节点是黑色</div></li><li><div>每个叶子节点都是黑色的空结点（NIL结点）（为了简单期间，一般会省略该节点）</div></li><li><div>如果一个节点是红色的，则它的子节点必须是黑色的（父子不能同为红）</div></li><li><div>从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点（平衡的关键）</div></li><li><div>新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行平衡</div></li></ol><div>在对红黑树进行添加或者删除操作时可能会破坏这些特点，所以红黑树采取了很多方式来维护这些特 点，从而维持平衡。主要包括：左旋转、右旋转和颜色反转</div><div><br/></div><div>左旋（RotateLeft） 逆时针旋转红黑树的两个结点，使得父结点被自己的右孩子取代，而自己成为自己的左孩子</div><div>右旋（RotateRight） 顺时针旋转红黑树的两个结点，使得父结点被自己的左孩子取代，而自己成为自己的右孩子</div><div><br/></div><div>颜色反转 就是当前节点与父节点、叔叔节点同为红色，这种情况违反了红黑树的规则，需要将红色向祖辈上传， 父节点和叔叔节点红色变为黑色，爷爷节点从黑色变为红色（爷爷节点必为黑色，因为此前是符合红黑 树规则的）。这样每条叶子结点到根节点的黑色节点数量并未发生变化，因此都其他树结构不产生影响</div><div><br/></div><div><br/></div><div>多路查找树(muitl-way search tree)，其每一个节点的孩子数可以多于两个，且每一个节点处可以存 储多个元素。</div><div>B树（BalanceTree）是对二叉查找树的改进。它的设计思想是，将相关数据尽量集中在一起，以便一 次读取多个数据，减少硬盘操作次数。</div><div><br/></div><div>一棵m阶的B 树 (m叉树)的特性如下： B</div><ol><li><div>树中所有节点的孩子节点数中的最大值称为B树的阶，记为M</div></li><li><div>树中的每个节点至多有M棵子树 ---即：如果定了M，则这个B树中任何节点的子节点数量都不能超</div></li><li><div>过M 若根节点不是终端节点，则至少有两棵子树</div></li><li><div>除根节点和叶节点外，所有点至少有m/2棵子树</div></li><li><div>所有的叶子结点都位于同一层</div></li></ol><div> B+树是B-树的变体，也是一种多路搜索树，其定义基本与B树相同，它的自身特征是： 非叶子结点的子树指针与关键字个数相同 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树 为所有叶子结点增加一个链指针 所有关键字都在叶子结点出现</div><div><br/></div><div>二叉堆本质上是一种完全二叉树，它分为两个类型</div><div>大顶堆(最大堆) 最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值</div><div>小顶堆(最小堆) 最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值</div><div>二叉堆的根节点叫作堆顶 最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小 元素</div><div>存储原理： 完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要 存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。</div><div><br/></div><div>排序：</div><div>根据时间复杂度的不同，主流的排序算法可以分为3大类</div><ol><li><div>时间复杂度为O( )的排序算法： 冒泡排序、选择排序、插入排序、希尔排序</div></li><li><div>时间复杂度为O(nlogn)的排序算法： 快速排序 、归并排序、堆排序</div></li><li><div>时间复杂度为线性的排序算法： 计数排序、桶排序、基数排序</div></li></ol><div>根据其稳定性，可以分为稳定排序和不稳定排序</div><div> 稳定排序：值相同的元素在排序后仍然保持着排序前的顺序 </div><div>不稳定排序：值相同的元素在排序后打乱了排序前的顺序</div><div><br/></div><div>冒泡排序是最基础的排序算法 冒泡排序的英文是bubble sort，它是一种基础的交换排序 冒泡排序这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧 移动。 按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位 置；当一个元素小于或等于右侧相邻元素时，位置不变。</div><div><br/></div><div>快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。 不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准 元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成 两个部分，这种思路就叫作分治法。</div><div>单边循环法只从数组的一边对元素进行遍历和交换。 开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置， 这个mark指针代表小于基准元素的区域边界。</div><div>堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。</div><div>堆是具有以下性质的完全二叉树</div><div>大顶堆：每个结点的值都大于或等于其左右孩子结点的</div><div>小顶堆：每个结点的值都小于或等于其左右孩子结点的值</div><div>我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中：</div><div>计数排序，这种排序算法是利用数组下标来确定元素的正确位置的。 假设数组中有10个整数，取值范围为0～10，要求用最快的速度把这10个整数从小到大进行排序。 可以根据这有限的范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为</div><div>桶排序同样是一种线性时间的排序算法 桶排序需要创建若干个桶来协助排序 每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素 桶排序的第1步，就是创建这些桶，并确定每一个桶的区间范围具体需要建立多少个桶，如何确定桶的 区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包 含数列最大值外， 前面各个桶的区间按照比例来确定。</div><div><br/></div><div>字符串匹配这个功能，是非常常见的功能，比如&quot;Hello&quot;里是否包含&quot;el&quot;? Java里用的是indexOf函数，其底层就是字符串匹配算法</div><div><br/></div><div>BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。 这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高</div><div>RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的 每次检查主串与子串是否匹配，需要依次比对每个字符，所以 BF 算法的时间复杂度就比较高，是 O(n*m)。我们对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低</div><div>思路： 通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式 串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这 里先不考虑哈希冲突的问题）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模 式串和子串比较的效率就提高了</div><div>BF 算法性能会退化的比较严重，而 RK 算法需要用到哈希算法，而设计一个可以应对各种类型字符的哈 希算法并不简单。 BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，滑动算法</div><div><br/></div><div>BM 算法包含两部分，分别是坏字符规则和好后缀规则<span style="color: unset; font-family: unset; font-size: unset;">。</span></div><div>坏字符规则 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的。</div><div><br/></div><div><br/></div><div>Trie 树，也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一 组字符串集合中快速查找某个字符串的问题。</div><div>当我们在 Trie 树中查找一个字符串的时候，比如查找字符串“her”，那我们将要查找的字符串分割成单 个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的 路径。</div><div>Trie 树是一个多叉树</div><div><br/></div><div>图，是一种复杂的非线性表结构。 图中的元素我们就叫做顶点图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边 跟顶点相连接的边的条数叫做度）</div><div>图这种结构有很广泛的应用，比如社交网络，电子地图，多对多的关系就可以用图来表示。 边有方向的图叫做有向图，比如A点到B点的直线距离，微信的添加好友是双向的 边无方向的图叫无向图，比如网络拓扑图 带权图（weighted graph）。在带权图中，每条边都有一个权重（weight），我们可以通过这个权重 来表示 一些可度量的值</div><div><br/></div><div>图最直观的一种存储方法就是，邻接矩阵（Adjacency Matrix）。 邻接矩阵的底层是一个二维数组</div><div><br/></div><div><br/></div><div>邻接表： 每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。 图中画的是一个有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。 前面的数组存储的是所有的顶点，每一个顶点后面连接的块代表前面顶点所指向的顶点和路线的权值。 如果该点还指向其他顶点，则继续在块后面添加。例如A指向了B权值是4，那么A后面就加上一块，之 后发现A还指向D权值是5，那么就在块尾继续添加一块。其实也就是数组+链表的结构</div><div><br/></div><div><br/></div><div>贪婪算法（Greedy）的定义：是一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望 导致结果是全局最好或最优的算法</div><div><br/></div><div>贪婪算法：当下做局部最优判断，不能回退 </div><div>（能回退的是回溯，最优+回退是动态规划） </div><div>由于贪心算法的高效性以及所求得答案比较接近最优结果，贪心算法可以作为辅助算法或解决一些要求 结果不特别精确的问题 </div><div>注意：当下是最优的，并不一定全局是最优的</div><div>贪心算法的关键是贪心策略的选择 将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品 按照我们的贪心策略，单位重量的价值排序： 物品A &gt; 物品B &gt; 物品C 因此，我们尽可能地多拿物品A，直到将物品1拿完之后，才去拿物品B，然后是物品C 可以只拿一部 分.....</div><div><br/></div><div>分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原 问题的解。</div><div><br/></div><div>分治和递归的区别：</div><ol><li><div>分治算法是一种处理问题的思想，递归是一种编程技巧</div></li><li><div>分治算法的递归实现中，每一层递归都会涉及三个操作</div></li><ol><li><div>分解：将原问题分解成一系列子问题</div></li><li><div>解决：递归地求解各个子问题，若子问题足够小，则直接求解</div></li><li><div>合并：将子问题的结果合并成原问题</div></li></ol></ol><div><br/></div><div>回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发 现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。 回溯的处理思想，有点类似枚举（列出所有的情况）搜索。我们枚举所有的解，找到满足期望的解。为 了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我 们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就 回退到上一个岔路口，另选一种走法继续走。</div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div></div></span>
</div></body></html> 